package main

import "fmt"

/*
归并排序
*/

func main() {
	test_array := []int{5, 9, 3, 5, 6, 7, 8, 44, 13534, 657, 886, 3, 7}
	result := mergeSort(test_array)
	fmt.Println(result)
}

func mergeSort(array []int) []int {
	if len(array) < 2 {
		return array
	}
	mid := len(array) / 2
	left := mergeSort(array[:mid])
	right := mergeSort(array[mid:])
	result := merge(left, right)
	return result
}

func merge(left, right []int) []int {
	leftIndex := 0
	rightIndex := 0
	result := []int{}
	for leftIndex < len(left) {
		if rightIndex == len(right) {
			result = append(result, left[leftIndex:]...)
			break
		}
		if left[leftIndex] <= right[rightIndex] {
			result = append(result, left[leftIndex])
			leftIndex++
		} else {
			result = append(result, right[rightIndex])
			rightIndex++
		}
	}
	result = append(result, right[rightIndex:]...)
	return result
}
